/// @tags: DP Expection
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int const N = 2e3 + 5, mod = 666623333, INF = 0x3f3f3f3f;

int n, m, x, q, l[N], r[N], f[N][N], sum[N][N], g[N], h[N], inv, ans;

struct Node {
  int l, r;
  inline bool operator<(Node const &rhs) const {
    return l < rhs.l || (l == rhs.l && r < rhs.r);
  }
} a[N], b[N];

inline LL qpow(LL base, int exp) {
  LL res = 1;
  while (exp) {
    if (exp & 1) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1;
  }
  return res;
}

inline int main() {
  int top = 0;
  cin >> n >> x >> q;
  for (int i = 1; i <= n; ++i) l[i] = INF, r[i] = -INF;
  for (int i = 1; i <= q; ++i) cin >> b[i].l >> b[i].r;
  sort(b + 1, b + q + 1);
  for (int i = 1; i <= q; ++i) {
    if (i > 1 && b[i].l == b[i - 1].l) continue;
    while (top && a[top].r >= b[i].r) top--;
    a[++top] = b[i];
  }
  q = top;
  for (int i = 1; i <= q; ++i)
    for (int j = a[i].l; j <= a[i].r; ++j) l[j] = min(l[j], i), r[j] = max(r[j], i);
  top = 0;
  for (int i = 1; i <= n; ++i)
    l[i] == INF ? (l[i] = top + 1, r[i] = top) : top = max(top, r[i]);
  f[0][0] = sum[0][0] = 1;
  top = 0;
  for (int i = 1; i <= n; ++i) {
    while (top < i - 1 && r[top] + 1 < l[i]) top++;
    for (int j = 1; j <= i; ++j)
      f[i][j] = (sum[i - 1][j - 1] - (top ? sum[top - 1][j - 1] : 0) + mod) % mod;
    for (int j = 0; j <= i; ++j)
      if ((sum[i][j] = sum[i - 1][j] + f[i][j]) >= mod) sum[i][j] -= mod;
  }
  for (int i = 1; i <= n; ++i)
    if (r[i] == q)
      for (int j = 1; j <= n; ++j) g[j] = (g[j] + f[i][j]) % mod;
  for (int i = 1; i <= x; ++i)
    for (int j = 1; j <= n; ++j)
      if ((h[i] += (LL)qpow(i, j) * qpow(x - i, n - j) % mod * g[j] % mod) >= mod)
        h[i] -= mod;
  for (int i = x; i >= 1; i--)
    if ((h[i] -= h[i - 1]) < 0) h[i] += mod;
  inv = qpow(qpow(x, n), mod - 2);
  for (int i = 1; i <= x; ++i)
    if ((ans += (LL)i * h[i] % mod * inv % mod) >= mod) ans -= mod;
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3600 随机数生成器.in", "r", stdin);
  freopen("P3600 随机数生成器.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
